/*
752. 打开转盘锁
https://leetcode.cn/problems/open-the-lock/description/
中等 2024/12/04
*/

class Solution {
public:
string test1(string s,int k)//向前
{
    int arr[4];
    string t;
    for(int i=0;i<4;i++)
    arr[i]=s[i]-'0';
    if(arr[k]==9) arr[k]=1;
    else arr[k]+=1;
    for(int i=0;i<4;i++)
         t+=arr[i]+'0';
    return t;
}

string test2(string s,int k)//向后
{
    int arr[4];
    string t;
    for(int i=0;i<4;i++)
    arr[i]=s[i]-'0';
    if(arr[k]==0) arr[k]=9;
    else arr[k]-=1;
    for(int i=0;i<4;i++)
         t+=arr[i]+'0';
    return t;
}

    int openLock(vector<string>& deadends, string target) {
        if(target == "0000") return 0;
        queue<pair<string,int>>qe;
        unordered_set<string>se;
        qe.emplace("0000",0);
        while(!qe.empty())
        {
            auto it=qe.front();
            qe.pop();
            string s=it.first;
            int ans=it.second;
            if(s==target) return ans;
            if(find(deadends.begin(),deadends.end(),s)==deadends.end())
            {
                for(int i=0;i<4;i++)//表示第几个位置滚动
                {
                    string t1=test1(s,i);
                    string t2=test2(s,i);
                    if(se.find(t1)==se.end())
                    {
                        se.insert(t1);
                        qe.emplace(t1,ans+1);
                    }
                    if(se.find(t2)==se.end())
                    {
                        se.insert(t2);
                        qe.emplace(t2,ans+1);
                    }                    
                }                
            }
        }
        return -1;
    }
};